# -*-coding = utf-8 -*-

# @Time: 2021/4/15 10:17
# @Author: bistro
# @File: p213.py
# @Software: PyCharm
# 213.打家劫舍 II
from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1 or n == 2 or n == 3:
            return max(nums)
        dp1 = [0] * n
        dp2 = [0] * n
        dp1[0] = nums[0]
        dp1[1] = max(nums[0], nums[1])
        for i in range(2, n-1):
            dp1[i] = max(dp1[i-2] + nums[i], dp1[i-1])
        dp2[1] = nums[1]
        dp2[2] = max(nums[1], nums[2])
        for j in range(3, n):
            dp2[j] = max(dp2[j - 2] + nums[j], dp2[j - 1])
        return dp1[-1] if dp1[-1] > dp2[-1] else dp2[-1]

    # 滚动数组
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1 or n == 2 or n == 3:
            return max(nums)
        prev = nums[0]
        next = max(nums[0], nums[1])
        for i in range(2, n-1):
            temp = next
            next = max(prev + nums[i], next)
            prev = temp
        prev1 = nums[1]
        next1 = max(nums[1], nums[2])
        for i in range(3, n):
            temp = next1
            next1 = max(prev1 + nums[i], next1)
            prev1 = temp
        return next if next > next1 else next1


s = Solution()
print(s.rob([2, 1, 1, 2]))
